home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 24 / CU Amiga Magazine's Super CD-ROM 24 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-07].iso / CUCD / Programming / SWI / source / lib / oset.pl < prev    next >
Encoding:
Text File  |  1997-05-06  |  4.8 KB  |  186 lines
  1. % Filename: oset.pl
  2. % Author--: Jon Jagger,  J.R.Jagger@shu.ac.uk
  3. % Created-: 05/03/93
  4. % Version-: 1.0
  5. % Updates-: Mon Oct 21 12:39:41 1996
  6. %        Fix in oset_int/3 by Robert van Engelen.
  7. % Notes---: This file provides some basic set manipulation
  8. %           predicates. The representation of the sets is
  9. %           assumed to be ordered with no duplication. You
  10. %           can create an ordered set from a free form list
  11. %           by using the sort/2 predicate. The advantage of
  12. %           using an ordered representation is that the algorithms
  13. %           are order sum of the sizes of the operands, rather than
  14. %           product of the sizes of the operands.
  15. %
  16. %           I have tried to make all the predicates as efficient as
  17. %           possible with respect to first argument indexing, and tail 
  18. %           clause determinacy.
  19. %
  20. %           These routines are provided as is, with no guarantees.
  21. %           They have undergone minimal testing.
  22.  
  23.  :- module(oset, [  oset_is/1,
  24.                     oset_union/3,
  25.                     oset_int/3,
  26.                     oset_diff/3,
  27.                     oset_dint/2,
  28.                     oset_dunion/2,
  29.                     oset_addel/3,
  30.                     oset_delel/3,
  31.                     oset_power/2
  32.                  ]).
  33.  
  34.  
  35. % oset_is(+OSet)
  36. %   check that OSet in correct format (standard order)
  37. % -------------------
  38. oset_is(-) :- !, fail.    % var filter
  39. oset_is([]).
  40. oset_is([H|T]) :-
  41.     oset_is(T, H).
  42.  
  43. oset_is(-, _) :- !, fail.  % var filter
  44. oset_is([], _H).
  45. oset_is([H|T], H0) :-
  46.     H0 @< H,               % use standard order
  47.     oset_is(T, H).
  48.  
  49.  
  50.  
  51. % oset_union(+OSet1, +OSet2, -Union).
  52. % -----------------------------
  53. oset_union([], Union, Union).
  54. oset_union([H1|T1], L2, Union) :-
  55.     union2(L2, H1, T1, Union).
  56.  
  57. union2([], H1, T1, [H1|T1]).
  58. union2([H2|T2], H1, T1, Union) :-
  59.     compare(Order, H1, H2),
  60.     union3(Order, H1, T1, H2, T2, Union).
  61.  
  62. union3(<, H1, T1,  H2, T2, [H1|Union]) :-
  63.     union2(T1, H2, T2, Union).
  64. union3(=, H1, T1, _H2, T2, [H1|Union]) :-
  65.     oset_union(T1, T2, Union).
  66. union3(>, H1, T1,  H2, T2, [H2|Union]) :-
  67.     union2(T2, H1, T1, Union).
  68.  
  69.  
  70. % oset_int(+OSet1, +OSet2, -Int)
  71. %   ordered set intersection
  72. % ------------------------------
  73. oset_int([], _Int, []).
  74. oset_int([H1|T1], L2, Int) :-
  75.     isect2(L2, H1, T1, Int).
  76.  
  77. isect2([], _H1, _T1, []).
  78. isect2([H2|T2], H1, T1, Int) :-
  79.     compare(Order, H1, H2),
  80.     isect3(Order, H1, T1, H2, T2, Int).
  81.  
  82. isect3(<, _H1, T1,  H2, T2, Int) :-
  83.     isect2(T1, H2, T2, Int).
  84. isect3(=, H1, T1, _H2, T2, [H1|Int]) :-
  85.     oset_int(T1, T2, Int).
  86. isect3(>, H1, T1,  _H2, T2, Int) :-
  87.     isect2(T2, H1, T1, Int).
  88.  
  89.  
  90. % oset_diff(+InOSet, +NotInOSet, -Diff)
  91. %   ordered set difference
  92. % --------------------------------------
  93. oset_diff([], _Not, []).
  94. oset_diff([H1|T1], L2, Diff) :-
  95.     diff21(L2, H1, T1, Diff).
  96.  
  97. diff21([], H1, T1, [H1|T1]).
  98. diff21([H2|T2], H1, T1, Diff) :-
  99.     compare(Order, H1, H2),
  100.     diff3(Order, H1, T1, H2, T2, Diff).
  101.  
  102. diff12([], _H2, _T2, []).
  103. diff12([H1|T1], H2, T2, Diff) :-
  104.     compare(Order, H1, H2),
  105.     diff3(Order, H1, T1, H2, T2, Diff).
  106.  
  107. diff3(<,  H1, T1,  H2, T2, [H1|Diff]) :-
  108.     diff12(T1, H2, T2, Diff).
  109. diff3(=, _H1, T1, _H2, T2, Diff) :-
  110.     oset_diff(T1, T2, Diff).
  111. diff3(>,  H1, T1, _H2, T2, Diff) :-
  112.     diff21(T2, H1, T1, Diff).
  113.  
  114.  
  115. % oset_dunion(+SetofSets, -DUnion)    
  116. %   distributed union
  117. % --------------------------------
  118. oset_dunion([], []).
  119. oset_dunion([H|T], DUnion) :-
  120.     oset_dunion(T, H, DUnion).
  121.  
  122. oset_dunion([], _DUnion, _DUnion).
  123. oset_dunion([H|T], DUnion0, DUnion) :-
  124.     oset_union(H, DUnion0, DUnion1),
  125.     oset_dunion(T, DUnion1, DUnion).
  126.  
  127.  
  128. % oset_dint(+SetofSets, -DInt)    
  129. %   distributed intersection
  130. % ---------------------------- 
  131. oset_dint([], []).
  132. oset_dint([H|T], DInt) :-
  133.     dint(T, H, DInt).
  134.  
  135. dint([], DInt, DInt).
  136. dint([H|T], DInt0, DInt) :-
  137.     oset_int(H, DInt0, DInt1),
  138.     dint(T, DInt1, DInt).
  139.  
  140.  
  141. % oset_power(+Set, -PSet)
  142. %   ordered set powerset
  143. % -----------------------
  144. oset_power(S, PSet) :-
  145.     pset(S, [[]], PSet0),
  146.     sort(PSet0, PSet).
  147.  
  148. pset([], PSet, PSet).
  149. pset([H|T], PSet0, PSet) :-
  150.     happ(PSet0, H, PSet1),
  151.     pset(T, PSet1, PSet).
  152.  
  153. happ([], _, []).
  154. happ([S|Ss], H, [[H|S],S|Rest]) :-
  155.     happ(Ss, H, Rest).
  156.  
  157.  
  158.  
  159. % oset_addel(+Set, +El, -Add)  
  160. %   ordered set element addition
  161. % ------------------------------
  162. oset_addel([], El, [El]). 
  163. oset_addel([H|T], El, Add) :-
  164.     compare(Order, H, El),
  165.     addel(Order, H, T, El, Add).
  166.  
  167. addel(<, H, T,  El, [H|Add]) :-
  168.     oset_addel(T, El, Add).
  169. addel(=, H, T, _El, [H|T]). 
  170. addel(>, H, T,  El, [El,H|T]).
  171.  
  172.  
  173. % oset_delel(+Set, +el, -Del)  
  174. %   ordered set element deletion
  175. % ------------------------------
  176. oset_delel([], _El, []).
  177. oset_delel([H|T], El, Del) :-
  178.     compare(Order, H, El),
  179.     delel(Order, H, T, El, Del).
  180.  
  181. delel(<,  H, T,  El, [H|Del]) :-
  182.     oset_delel(T, El, Del).
  183. delel(=, _H, T, _El, T).
  184. delel(>,  H, T, _El, [H|T]).
  185.  
  186.